CLASSIFIERS BASED ON BAYES DECISION THEORY

Introduction

In this unit, we discuss classifiers based on Bayesian decision theory, which are based on the idea of design classifiers that classify an unknown pattern in the most probable class. So the So the question is how to define what most probable means.

Given a classification task of $M$ classes, $\omega_1, \omega_2, \ldots, \omega_M$, and an unknown pattern, which is represented by a feature vector $x$, we form the $M$ conditional probabilities $$P(\omega_i|X=x), \ i=1,2,\ldots,M$$ that is, the probability that the unknown pattern belongs to the respective class $\omega_i$, given that we know its feature vector takes the value $x$. These are also referred to as a posteriori probabilities.

The classifiers based on Bayes decision theory quantify the most probable class, by computing either the maximum of these $M$ values or, equivalently, the maximum of an appropriately defined function of them. The unknown pattern is then assigned to the class corresponding to this maximum

Bayes Decision Theory

We will initially focus on the two-class case. Let $\omega_1$, $\omega_2$ be the two classes in which our patterns belong.

We assume that the a priori probabilities $P(\omega_1)$ $P(\omega_2)$ are known. This is a reasonable assumption, because even if they are not known exactly, they can easily be estimated from the available training feature vectors.

If $N$ is the total number of available training patterns, and $N_1$ $N_2$ of them belong to $\omega_1$ and $\omega_2$, respectively, then

$$P(\omega_1) \approx \frac{N_1}{N}$$$$P(\omega_2) \approx \frac{N_2}{N}$$

We also assume that the class-conditional probability density functions

$$p(x | \omega_i), \ i=1,2$$

are known. These describe the distribution of the known feature vectors in each of the classes.

If these are not known, they can also be estimated from the available training data.

The pdf (probability density function) is sometimes referred to as the likelihood function of $\omega_i$ with respect to $x$. If the feature vectors can take only discrete values, density functions $p(x | \omega_i)$ become probabilities (mass probability function) and will be denoted by $P(x| \omega_i)$.

Using Bayes' rule, we can calculate the conditional probabilities: $$P(\omega_i | X=x) = \frac{p(x| \omega_i)P(\omega_i)}{p(x)}$$ where $p(x)$ is the pdf of $x$ and for which we have $$p(x) = \sum_{i=1}^2 p(x|\omega_i) P(\omega_i)$$

The Bayes classification rule can now be stated as:

$$\text{If} \qquad P(\omega_1 | x) > P(\omega_2 | x), \ x \rightarrow \omega_1$$$$\text{If} \qquad P(\omega_1 | x) < P(\omega_2 | x), \ x \rightarrow \omega_2$$

In the case of equality, $P(\omega_1|x) = P(\omega_2|x)$, the pattern is arbitrarily assigned to one of the two classes.

So the only task is to estimate:

• $P(\omega_i)$ (priori probabilities)
• $p(x|\omega_i)$ (likelihood function of $\omega_i$ with respect to $X$)

Using Bayes' rule, the decision can equivalently be based on the inequalities $$p(x|\omega_1) P(\omega_1) \gtrless p(x|\omega_2) P(\omega_2)$$ $p(x)$ is not taken into account, because it is the same for all classes and it does not affect the decision.

Example

Iris dataset

It is a dataset about 3 types of flowers:

• Setosa
• Versicolor
• Virginica

Which contains information on 4 features of each flower:

• Length and width of the sepal
• Length and width of the petal

The data was collected by botanist Edgar Anderson and used by statistician Ronald Fischer to show an example of his linear discriminant analysis.

Let $$X : \Omega \rightarrow \mathbb{R}^2$$ be a random vector that represent 2 features of a pattern set.

We assume that each pattern in $\Omega$ belongs to a class to a specific class:

• Setosa ($\omega_1$).
• Versicolor ($\omega_2$).
• Virginica ($\omega_3$).

Estimated density function of $X$ $$p(\textbf{x})$$

Probability of each class (priori probabilities) $$P(\omega_i)$$

Probability of class 0: 0.3333333333333333
Probability of class 1: 0.3333333333333333
Probability of class 2: 0.3333333333333333

Class-conditional probability density functions $$p(x|\omega_i)$$

Bayesian classification rule

Clase 0: [0.04133813]
Clase 1: [0.01247693]
Clase 2: [0.00812357]

Appendix

Definition: Conditional Probability

Let $(\Omega, \mathscr{F}, P)$ be a probability space and let $B\in \mathscr{F}$ be an event such that $P(B)>0$.

For any $A\in \mathscr{F}$, we define the conditional probability of $A$ given $B$, that we will denote $P(A|B)$ by $$P(A|B) = \frac{P(A\cap B)}{P(B)}$$

Proposition

Let ($\Omega, \mathscr{F}, P)$ be a probability space and let $B\in \mathscr{F}$ be an event such that $P(B)>0$. Then

1. $P(\cdot|B)$ is a probability measure on the measurable space $(B, \mathscr{F}_B)$, where $\mathscr{F}_B=\{A\cap B | A\in \mathscr{F}\}$.
2. If $A$ and $B$ are independent events, then

$$P(A|B) = P(A)$$

3. [Bayes' rule] If $\{A_i\}_{i=1}^n \subset \mathscr{F}$ is a measurable partition of $\Omega$, such that $P(A_i) > 0, \ i=1,\ldots,n$. Then

$$P(A_i | B) = \frac{P(A_i) P(B|A_i)}{\sum_{k=1}^n P(A_k) P(B|A_k)}, \qquad \forall i=1,\ldots,n$$

Proof of Bayes' rule

• Let $\{A_i\}_{i=1}^n \subset \mathscr{F}$ be a measurable partition of $\Omega$, such that $P(A_i)>0$ for every $i=1,\ldots,n$.
• Then $\Omega = \cup_{i=1}^n A_i$ and the $A_i'$s are disjoint.
• Then $$P(B) = P(\Omega \cap B)= \sum_{i=1}^n P(A_i \cap B)$$
• Therefore

$$\begin{align} P(A_i|B) &=& \frac{P(A_i\cap B)}{P(B)}\\ &=& \frac{P(B|A_i)P(A_i)}{\sum_{k=1}^n P(A_k \cap B) } \\ &=& \frac{P(B|A_i)P(A_i)}{\sum_{k=1}^n P(B|A_k) P(A_k)}\end{align}$$

and Bayes' rule is proved.

For case $\{A_1, A_2\}$, Bayes' rule ensures that $$P(A_1| B) = \frac{P(B|A_1)P(A_1)}{P(B|A_1)P(A_1)+P(B|A_2)P(A_2)}$$ equivalently for $P(A_2|B)$

References

• González-Barrios Murguía, J.M. (2011). Lecture Notes on Probability Theory, UNAM-IIMAS.
• Theodoridis, S. & Koutroumbas, K. (2009) Pattern Recognition, 4th ed., Academic Press.

Minimizing the classification error probability

Let $R_1$ be the region of the feature space in which we decide in favor of $\omega_1$ and $R_2$ be the corresponding region for $\omega_2$.

Then an error is made if $x \in R_1$, although it belongs to $\omega_2$ or if $x \in R_2$, although it belongs to $\omega_1$. That is, $$P_e = P(x\in R_2, \omega_1) + P(x\in R_1, \omega_2)$$ Where $P(\cdot,\cdot)$ is the joint probability of two events.

By definition, the conditional probability of $B$ assuming $A$ is $$P(B|A) = \frac{P(B,A)}{P(A)}$$

Therefore, the total error becomes \begin{align} P_e &=& P(x\in R_2 | \omega_1) P(\omega_1)+P(x\in R_1 | \omega_2) P(\omega_2)\\ &=& P(\omega_1) \int_{R_2} p(x|\omega_1)dx + P(\omega_2) \int_{R_1} p(x|\omega_2)dx\tag{eq1} \end{align} Where $ p(x|\omega_1)$ is the conditional probability density function of $x$ given $\omega_1$, which describes how the values of $x$ are distributed within the class $\omega_1$.

Bayes' rule states that $$P(\omega_1 | x) = \frac{p(x|\omega_1)P(\omega_1)}{p(x)}$$

Factoring we obtain $$P(\omega_1|x)p(x)= p(x|\omega_1)P(\omega_1) = P(x, \omega_1) $$

Substituting in (eq1), we have that $$P_e = \int_{R_2} P(\omega_1|x)p(x)dx+\int_{R_1} P(\omega_2|x)p(x)dx \tag{eq2}$$

By the law of total probability $$P(\omega_1) = \int_{\Omega} P(\omega_1 | x) p(x) dx$$

Since the uniont of the regions $R_1$, $R_2$ partition the space, that is $\Omega = R_1 \cup R_2$ and $R_1 \cap R_2=\emptyset$, we have that \begin{align} P(\omega_1) &=& \int_{R_1 \cup R_2} P(\omega_1|x) p(x)dx \\ &=& \int_{R_1} P(\omega_1|x) p(x)dx + \int_{R_2} P(\omega_1|x) p(x)dx\end{align} Then, $$\int_{R_2} P(\omega_1|x)p(x)dx= P(\omega_1)-\int_{R_1}P(\omega_1|x)p(x)dx$$

Substituting in (eq2), we obtain \begin{align} P_e &=& \left( P(\omega_1)-\int_{R_1}P(\omega_1|x)p(x)dx \right)+\int_{R_1} P(\omega_2|x)p(x)dx\\ &=& P(\omega_1)+\int_{R_1} \left(-P(\omega_1|x) +P(\omega_2 | x) \right)p(x) dx\\ &=&P(\omega_1)-\int_{R_1} \left(P(\omega_1|x) -P(\omega_2 | x) \right)p(x) dx \end{align}

Because the first element is fixed, $P(\omega_1)$, the error is minimized when the value of the integral is larger. This occurs when $R_1$ is the region of space in which $$P(\omega_1 |x) > P(\omega_2 |x)$$

Then, $R_2$ becomes the region where the reverse is true. In other words, when $$P(\omega_2 |x ) > P(\omega_1|x)$$

Therefore, the error is minimized if the partitioning regions $R_1$ and $R_2$ of the feature space are chosen so that $$R_1: \qquad P(\omega_1|x) > P(\omega_2|x)$$ $$R_2: \qquad P(\omega_2 |x) > P(\omega_1|x)$$

$M$-classes

So far, we have dealt with the simple case of two classes. Generalizations to the multiclass case are straightforward. In a classification task with $M$ classes, $\omega1, \omega_2,\ldots, \omega_M$, an unknown pattern, represented by the feature vector $x$, is assigned to class $\omega_i$ if $$P(\omega_1 | x) > P(\omega_j |x), \qquad \forall j\neq i$$

It can be shown that such a choice also minimizes the probability of classification error.

Discriminant functions

It is by now clear that minimizing either the error probability is equivalent to partitioning the feature space into $M$ regions, for a task with $M$ classes.

If regions $R_i$, $R_j$ happen to be contiguous, then they are separated by a decision surface in the multidimensional feature space. For the minimum error probability case, this is described by the equation $$P(\omega_i | x) - P(\omega_j|x) = 0$$

From the one side of the surface this difference is positive, and from the other it is negative.

Sometimes, instead of working directly with probabilities, it may be more convenient, from a mathematical point of view, to work with an equivalent function of them, for example, $$g_i(x) \equiv f (P(\omega_i |x))$$ where $f(\cdot)$ is a monotonically increasing function. $g_i(x)$ is known as a discriminant function.

The decision test $$P(\omega_i|x) > P(\omega_j|x) \qquad \forall j\neq i$$ is now stated as $$\text{classify} \ x \ \text{in} \ \omega_i \quad \text{if} \quad g_i(x) > g_j(x) \quad j\neq i$$

The decision surfaces, separating contiguous regions, are described by $$g_{ij}(x) \equiv g_i(x) - g_j(x) = 0, \qquad i,j=1,2,\ldots,M, \ i\neq j$$

So far, we have approached the classification problem via Bayesian probabilistic approache and the goal was to minimize the classification error probability or the risk.

However, as we will soon see, not all problems are well suited to such approaches.

For example, in many cases the involved pdfs are complicated and their estimation is not an easy task.

In such cases, it may be preferable to compute decision surfaces directly by means of alternative costs.

Such approaches give rise to discriminant functions and decision surfaces, which are entities with no (necessary) relation to Bayesian classification, and they are, in general, suboptimal with respect to Bayesian classifiers.

BAYESIAN CLASSIFICATION FOR NORMAL DISTRIBUTIONS

The Gaussian Probability Density Function

One of the most commonly encountered probability density functions in practice is the Gaussian or normal probability density function. The major reasons for its popularity are its computational tractability and the fact that it models adequately a large number of cases.

The one-dimensional or the univariate Gaussian, as it is sometimes called, is defined by $$p(x) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2} \right)$$ With parameters $\mu$ (mean) and $\sigma^2$ (variance).

The multivariate generalization of a Gaussian pdf in the l-dimensional space is given by $$p(x) = \frac{1}{(2\pi)^{\frac{l}{2}}|\Sigma|^{\frac{1}{2}}}\exp\left(-\frac{1}{2}(x-\mu)^T \Sigma^{-1}(x-\mu) \right)$$ where $\mu = E[x]$ is the mean value and $\Sigma$ is the $l\times l$ covariance matrix defined as $$\Sigma = E\left[ (x-\mu)(x-\mu)^T\right]$$ where $|\Sigma|$ denotes the determinant of $\Sigma$.

It is readily seen that for $l=1$ the multivariate Gaussian coincides with the univariate one.

The symbol $N(\mu,\Sigma)$ is used to denote a Gaussian pdf with mean value $\mu$ and covariance $\Sigma$.

$\sigma_{XX}$ lo hace ancho
$\sigma_{YY}$ lo hace largo
$\sigma_{XY}$ lo incilna, para arriba cuando es positivo y para abajo cuando es negativo

The Bayesian Classifier for Normally Distributed Classes

The optimal Bayesian classifier when the involved pdfs, $p(x|\omega_i), \ i=1,2,\ldots,M$ (likelihood functions of $\omega_i$ with respect to $x$), describing the data distribution in each one of the classes, are multivariate normal distributions, that is, $$N(\mu_i, \Sigma_i), \ i=1,2,\ldots,M$$

Because of the exponential form of the involved densities, it is preferable to work with the following discriminant functions, which involve the (monotonic) logarithmic function $\ln(\cdot)$:

\begin{align} g_i(x) &=& \ln\left(p(x|\omega_i)P(\omega_i) \right)\\ &=&\ln p(x|\omega_i) + \ln P(\omega_i)\\ &=& \ln\left(\frac{1}{(2\pi)^{\frac{l}{2}}|\Sigma_i|^{\frac{1}{2}}}\exp\left(-\frac{1}{2}(x-\mu_i)^T \Sigma_i^{-1}(x-\mu_i) \right) \right)+ \ln P(\omega_i)\\ &=& \ln\left(\frac{1}{(2\pi)^{\frac{l}{2}}|\Sigma_i|^{\frac{1}{2}}}\right) + \ln\left(\exp\left(-\frac{1}{2}(x-\mu_i)^T \Sigma_i^{-1}(x-\mu_i) \right) \right)+ \ln P(\omega_i)\\ &=& c_i-\frac{1}{2}(x-\mu_i)^T \Sigma_i^{-1}(x-\mu_i) + \ln P(\omega_i) \\ \end{align}

where $c_i$ is a constant $c_i = -\frac{l}{2}\ln(2\pi)-\frac{1}{2}\ln |\Sigma_i|$.

Expanding, we obtain $$g_i=-\frac{1}{2}x^T \Sigma_i^{-1} x + \frac{1}{2} x^T \Sigma_i^{-1}\mu_i +\frac{1}{2}\mu_i^T \Sigma_i^{-1}x-\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mu_i +\ln P(\omega_i) + c_i \tag{eq1}$$

In general, this is a nonlinear quadratic form.

Take, for example, the case of $l=1$ and assume that $$\Sigma_i = \left[\begin{matrix} \sigma_i^2 & 0 \\ 0 & \sigma_i^2\end{matrix}\right]$$ Then, eq1 becomes $$g_i(x) = -\frac{1}{2\sigma_i^2}(x_1^2+x_2^2) + \frac{1}{\sigma_i^2}(\mu_{i1}x_1+\mu_{i2}x_2)-\frac{1}{2\sigma_i^2}(\mu_{i1}^2+\mu_{i2}^2) + \ln P(\omega_i) +c_i$$

and obviously the associated decision curves $$g_i(x)-g_j(x)=0$$ are quadrics: ellipsoids, parabolas, hyperbolas, pairs of lines.

That is, in such cases, the Bayesian classifier is a quadratic classifier, in the sense that the partition of the feature space is performed via quadric decision surfaces. For $l>2$ the decision surfaces are hyperquadrics.

Decision Hyperplanes

The only quadratic contribution in eq1 comes from the term $x^T \Sigma_i^{-1} x$. If we now assume that the covariance matrix is the same in all classes, that is, $\Sigma_i = \Sigma$, the quadratic term will be the same in all discriminant functions.

Hence, it does not enter into the comparison for computing the maximum, and it cancels out in the decision surface equations.

The same is true for the constant $c_i$. Thus, they can be omitted, and we may redefine $g_i(x)$ as $$g_i(x) = w_i^T x + w_{i0}$$ where \begin{align} w_i &=& \Sigma^{-1}\mu_i\\ w_{i0} &=& \ln P(\omega_i) -\frac{1}{2} \mu_i^T \Sigma^{-1}\mu_i \end{align} Hence $g_i(x)$ is a linear function of $x$ and the respective decision surface are hyperplanes

Cuando tienen la misma $\sigma_{XX}$ y $\sigma_{YY}$ se hace una recta

The Naive-Bayes Classifier

To implement a Bayesian classifier it is necessary to estimate the probability density functions $p(x | \omega_i), i=1,2,\ldots,M$, which correspond to multivariate distributions since $$x\in \mathbb{R}^l$$

In order to sato safeguard good estimates of the pdfs the number of training samples, $N$, must be large enough. To this end, the demand for data increases exponentially fast with the dimension of the feature space $l$.

Crudely speaking, if N could be regarded as a good number of training data points for obtaining sufficiently accurate estimates of a pdf in an one-dimensional space, then $N^l$ points would be required for an $l$-dimensional space.

Thus, large values of $l$ make the accurate estimation of a multidimensional pdf a bit of an illusion since in practice data is hard to obtain.

To resolve this issue, concessions can be made about the degree of accuracy that is expected from the pdf estimates.

One widely used approach is to assume that individual features (components of the random vector) $x_j, \ j=1,2,\ldots,l$, are statistically independent.

Under this assumption, we can write

$$p(x|\omega_i) = \prod_{j=1}^{l} p(x_j|\omega_i), \qquad i=1,2,\ldots,M$$

The scenario is now different. To estimate $l$ one-dimensional pdfs, for each of the classes, $lN$ data points would be enough in order to obtain good estimates, instead of $N^l$ . This leads to the so-called naive-Bayes classifier, which assigns an unknown sample $x=[x_1,x_2,\ldots,x_l]^T$ to the class (Naive-Bayes Classifier): $$\omega_m = \arg \max_{\omega_i} \prod_{j=1}^l p(x_k|\omega_i), \qquad i=1,2,\ldots,M$$

In practices, the naive-Bayes classifier can be very robust to violations of its independence assumption, and it has been reported to perform well many real-world data sets.

Examples*

Exercise

17

[1. 2.]
[[1.33333333 0.66666667]
 [0.66666667 3.33333333]]
[4. 2.]
[[0.75 0.  ]
 [0.   0.75]]
[2. 5.]
[[5.33333333 0.        ]
 [0.         1.33333333]]

$X_1$	$X_2$	$X_3$	$Y$
1	0	25	1
0	1	35	0
1	1	35	1
0	0	18	0
1	1	40	1
0	0	25	0
1	0	30	1
0	1	20	1
1	1	30	1
1	0	18	0

Tenemos $\omega_0$ que son a los que no se les dió crédito y a los que sí $\omega_1$. Calculamos sus probabilidades:

$$\mathbb{P}[\omega_0] = \frac{4}{10} $$$$\mathbb{P}[\omega_1] = \frac{6}{10} $$

Probabilidades Condicionales

Tabla de los que sí les dieron crédito

$X_1$	$X_2$	$X_3$	$Y$
1	0	25	1
1	1	35	1
1	1	40	1
1	0	30	1
0	1	20	1
1	1	30	1

Para $X_1$: $$\mathbb{P}[X_1 = 1 | \omega_1] = \frac{5}{6}$$ $$\mathbb{P}[X_1 = 0 | \omega_1] = \frac{1}{6}$$

Para $X_2$: $$\mathbb{P}[X_2 = 1 | \omega_1] = \frac{4}{6}$$ $$\mathbb{P}[X_2 = 0 | \omega_1] = \frac{2}{6}$$

Para $X_3$:

Asumimos que es normal

$$\mathbb{P}[X_3 = x | \omega_1] = N(\mu, \sigma)$$$$ \bar{x} = 30 $$$$ s^2 = 50 $$$$ s = 7.07 $$

Tabla de los que no les dieron crédito

$X_1$	$X_2$	$X_3$	$Y$
0	1	35	0
0	0	18	0
0	0	25	0
1	0	18	0

Para $X_1$: $$\mathbb{P}[X_1 = 1 | \omega_0] = \frac{1}{4}$$ $$\mathbb{P}[X_1 = 0 | \omega_0] = \frac{3}{4}$$

Para $X_2$: $$\mathbb{P}[X_2 = 1 | \omega_0] = \frac{1}{4}$$ $$\mathbb{P}[X_2 = 0 | \omega_0] = \frac{3}{4}$$

Para $X_3$:

Asumimos que es normal

$$\mathbb{P}[X_3 = x | \omega_1] = N(\mu, \sigma)$$$$ \bar{x} = 24 $$$$ s^2 = 64 $$$$ s = 8.04 $$

Queremos calcular de otro patron

$X_1$	$X_2$	$X_3$	$Y$
1	0	21	??

$$ \begin{align*} \text{Le damos el crédito} & \quad \text{vs} \quad \text{No damos el crédito} \\ P(\omega_1 |x) & \quad \text{vs} \quad P(\omega_2 |x) \\ P(X| \omega_1)P(\omega_1) & \quad \text{vs} \quad P(X| \omega_0)P(\omega_0) \\ \prod_{i = 1}^M P(X_i = x| \omega_1)P(\omega_1) & \quad \text{vs} \quad \prod_{i = 1}^M P(X_i = x| \omega_0)P(\omega_0) \\ P(X_1 = 1| \omega_1)P(X_2 = 0| \omega_1)P(X_3 = 21| \omega_1)P(\omega_1) & \quad \text{vs} \quad P(X_1 = 1| \omega_0)P(X_2 = 0| \omega_0)P(X_3 = 21| \omega_0)\\ \left(\frac{5}{6}\right)\left(\frac{2}{6}\right) \mathcal{N}(21 \mid 30,7.07)\left(\frac{6}{10}\right) & \quad \text{vs} \quad \left(\frac{1}{4}\right)\left(\frac{3}{4}\right)\mathcal{N}(21 \mid24,8.04)\left(\frac{4}{10}\right)\\ \left(\frac{5}{6}\right)\left(\frac{2}{6}\right) (0.02509)\left(\frac{6}{10}\right) & \quad \text{vs} \quad \left(\frac{1}{4}\right)\left(\frac{3}{4}\right)(0.04628)\left(\frac{4}{10}\right)\\ 0.0041816 & \quad \text{vs} \quad 0.003471 \\ \end{align*} $$

$$\omega_m = \arg \max_{\omega_i} \prod_{j=1}^l p(x_k|\omega_i), \qquad i=1,2,\ldots,M$$

El más grande es 1, entonces le damos el crédito

Apéndice

Normal

$$ \mathcal{N}(\mu, \sigma) = \frac{1}{\sigma \sqrt{2\pi}} e^{-\frac{1}{2} \left(\frac{x - \mu}{\sigma}\right)^2} $$$$ \bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i $$$$ s = \sqrt{\frac{1}{n-1} \sum_{i=1}^{n} (x_i - \bar{x})^2} $$

Poisson

$$ P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!} $$$$ \mu = \lambda $$$$ \sigma^2 = \lambda $$